package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC127 {

    /**
     * Input:
     * beginWord = "hit",
     * endWord = "cog",
     * wordList = ["hot","dot","dog","lot","log","cog"]
     * Output: 5
     * Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     * return its length 5.
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }

        if (!wordList.contains(beginWord)) {
            wordList.add(beginWord);
        }

        int len = wordList.size();
        int[][] adjMat = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i == j) {
                    continue;
                } else if (j < i) {
                    adjMat[i][j] = adjMat[j][i];
                } else {
                    adjMat[i][j] = getDistance(wordList.get(i), wordList.get(j));
                }
            }
        }

        int step = Dijkstra(adjMat, wordList.indexOf(beginWord), wordList.indexOf(endWord));
        return step > IMAX ? 0 : step;
    }


    public int getDistance(String s, String d) {
        if (s.length() != d.length()) {
            return IMAX;
        }

        int diffCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != d.charAt(i)) {
                ++diffCount;
            }
        }

        return diffCount == 1 ? 1 : IMAX;
    }


    private static int IMAX = Integer.MAX_VALUE - 10; //不连通状态

    public static int Dijkstra(int[][] martix, int start, int terminal) {
        boolean[] isVisted = new boolean[martix.length];
        int[] d = new int[martix.length];
        for (int i = 0; i < martix.length; i++) {
            isVisted[i] = false; //该点是否被计入，可以理解为判断该点是否已经加入集合B
            d[i] = IMAX;//在当前的集合B所能连接的路径中，从起始点到该点的最短路径
        }
        isVisted[start] = true;
        d[start] = 0;
        int unVisitNode = martix.length;
        int index = start;
        while (unVisitNode > 0 && !isVisted[terminal]) {
            int min = IMAX;
            //选出集合A中的点到集合B的路径最短的点
            for (int i = 0; i < d.length; i++) {
                if (min > d[i] && !isVisted[i]) {
                    index = i;
                    min = d[i];
                }
            }


            for (int i = 0; i < martix.length; i++) {
                if (d[index] + martix[index][i] < d[i]) //更新当前的最短路径
                    d[i] = d[index] + martix[index][i];
            }

            unVisitNode--;
            isVisted[index] = true;
        }

        return d[terminal] + 1;
    }

    public int ladderLength_BFS(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }

        int step = 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (endWord.equals(cur)) return step + 1;
                char[] curArray = cur.toCharArray();
                for (int j = 0; j < curArray.length; j++) {
                    for (int k = 0; k < 26; k++) {
                        if (curArray[j] == ('a' + k)) continue;
                        char temp = curArray[j];
                        curArray[j] = (char) ('a' + k);
                        String next = new String(curArray);
                        if (dict.contains(next)) {
                            queue.offer(next);
                            dict.remove(next);
                        }
                        curArray[j] = temp;
                    }
                }
            }

            ++step;
        }

        return 0;
    }

    public static void main(String[] args) {

//        int[][] adjMat = {
//                {0, 1, 3, 6},
//                {1, 0, IMAX, 6},
//                {3, IMAX, 0, 2},
//                {6, 6, 2, 0}
//        };
//        Dijkstra(adjMat, 0, 3);


        LC127 an = new LC127();
        String be = "hit", end = "cog";
        List<String> li = Arrays.asList(InputUtil.toStringArray("[\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]"));
//        List<String> li = new ArrayList<>(Arrays.asList("hot", "dog"));
        System.out.println(an.ladderLength_BFS(be, end, li));
    }
}
